#pragma once

#ifdef __WIN32
#include <windows.h>
#else
#include <sys/mman.h> // mmap 函数和相关标志（如 MAP_ANONYMOUS、PROT_READ 等）
#endif

#include <iostream>
#include <vector>
#include <time.h>
#include <assert.h>
#include <mutex>
#include <algorithm>
#include <unordered_map>
using std::cout;
using std::endl;

static const size_t MAX_BYTES = 1024 * 256;
static const size_t NFREE_LIST = 208;
static const size_t NPAGES = 128;
// 页大小转换偏移，即一页定义为2^13，也就是8KB,linux下要调为12
static const size_t PAGE_SHIFT = 12;

inline static void *SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void *ptr = VirtualAlloc(0, kpage << PAGE_SHIFT, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else

	void *ptr = mmap(
		nullptr,					 // 由内核选择分配地址
		kpage * (1 << PAGE_SHIFT),	 // 分配大小 = kpage * 页大小（如 8KB）
		PROT_READ | PROT_WRITE,		 // 内存可读可写
		MAP_PRIVATE | MAP_ANONYMOUS, // 私有匿名映射（不关联文件）
		-1,							 // 文件描述符（匿名映射设为-1）
		0							 // 偏移量（无需偏移）
	);
	if (ptr == MAP_FAILED)
	{				   // mmap 失败返回 MAP_FAILED
		ptr = nullptr; // 统一设置为 nullptr
	}
#endif
	if (ptr == nullptr)
	{
		throw std::bad_alloc(); // 统一抛出异常
	}
	return ptr;
}

#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#else
// Linux/macOS等POSIX系统
#include <sys/types.h>
typedef uintptr_t PAGE_ID; // 或使用 `unsigned long`（需验证平台匹配性）
#endif

// 管理切分好的小对象的自由链表
class FreeList
{
public:
	// 将释放的对象头插到自由链表
	void Push(void *obj)
	{
		assert(obj);
		// 头插
		*(void **)obj = _freeList;
		_freeList = obj;
		_size++;
	}

	// 从自由链表头部获取一个对象
	void *Pop()
	{
		assert(_freeList);
		// 头删
		void *obj = _freeList;
		_freeList = *(void **)obj;
		_size--;
		return obj;
	}
	void PushRange(void *start, void *end, size_t n)
	{
		*(void **)end = _freeList;
		_freeList = start;
		_size += n;
	}
	void PopRange(void *&start, void *&end, size_t size)
	{
		assert(size <= _size);
		start = _freeList;
		end = start;
		while (size--)
		{
			end = *(void **)start;
		}
		_freeList = *(void **)(end); // 自由链表指向end的下一个对象
		*(void **)(end) = nullptr;	 // 取出的一段链表的表尾置空
		_size -= size;
	}

	size_t size()
	{
		return _size;
	}
	bool Empty()
	{
		return _freeList == nullptr;
	}
	size_t &MaxSize()
	{
		return _maxsize;
	}

private:
	void *_freeList = nullptr; // 自由链表
	size_t _maxsize = 1;
	size_t _size = 0;
};

class sizeclass
{
public:
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	{
		return (bytes + alignNum - 1) & ~(alignNum - 1);
	}

	// bytes: 需要分配的内存字节数，需要减去上个区间的字节数，因为我们计算的映射值是区间的第几位
	// alignShift: 对齐位移，表示内存块大小的基数为 2^alignShift（如 alignShift=3 时，块大小为 8B）
	static inline size_t _Index(size_t bytes, size_t alignShift)
	{
		return ((bytes + (1 << alignShift) - 1) >> alignShift) - 1;
	}

public:
	// 整体控制在最多10%左右的内碎⽚浪费
	// [1,128]                    8byte对⻬                   freelist[0,16)
	// [128+1,1024]               16byte对⻬                 freelist[16,72)
	// [1024+1,8*1024]            128byte对⻬                 freelist[72,128)
	// [8*1024+1,64*1024]         1024byte对⻬                freelist[128,184)
	// [64*1024+1,256*1024]       8*1024byte对⻬              freelist[184,208)

	static inline size_t RoundUp(size_t bytes)
	{
		if (bytes <= 128)
		{
			return _RoundUp(bytes, 8);
		}
		else if (bytes <= 1024)
		{
			return _RoundUp(bytes, 16);
		}
		else if (bytes <= 8 * 1024)
		{
			return _RoundUp(bytes, 128);
		}
		else if (bytes <= 64 * 1024)
		{
			return _RoundUp(bytes, 1024);
		}
		else if (bytes <= 256 * 1024)
		{
			return _RoundUp(bytes, 8 * 1024);
		}
		else
		{
			// 大于256KB的按页对齐
			return _RoundUp(bytes, 1 << PAGE_SHIFT);
		}
	}

	// 获取对应哈希桶的下标
	static inline size_t Index(size_t bytes)
	{
		// 每个区间有多少个自由链表
		static size_t groupArray[4] = {16, 56, 56, 56};
		if (bytes <= 128)
		{
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			return _Index(bytes - 128, 4) + groupArray[0];
		}
		else if (bytes <= 8 * 1024)
		{
			return _Index(bytes - 1024, 7) + groupArray[0] + groupArray[1];
		}
		else if (bytes <= 64 * 1024)
		{
			return _Index(bytes - 8 * 1024, 10) + groupArray[0] + groupArray[1] + groupArray[2];
		}
		else if (bytes <= 256 * 1024)
		{
			return _Index(bytes - 64 * 1024, 13) + groupArray[0] + groupArray[1] + groupArray[2] + groupArray[3];
		}
		else
		{
			assert(false);
			return -1;
		}
	}

	// thread cache一次从central cache获取对象的数目
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);

		// 对象越小，计算出的上限越高
		// 对象越大，计算出的上限越低
		int num = MAX_BYTES / size;
		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;

		return num;
	}

	// central cache一次向page cache获取多少页
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size); // 计算出thread cache一次向central cache申请对象的个数上限
		size_t nPage = num * size;		// num个size大小的对象所需的字节数

		nPage >>= PAGE_SHIFT; // 将字节数转换为页数
		if (nPage == 0)		  // 至少给一页
			nPage = 1;

		return nPage;
	}
};

struct Span
{
	PAGE_ID _pageId = 0; // 大块内存起始页的页号
	size_t _n = 0;		 // 页的数量

	Span *_next = nullptr; // 双链表结构
	Span *_prev = nullptr;

	size_t _useCount = 0;	   // 切好的小块内存，被分配给thread cache的计数
	void *_freeList = nullptr; // 切好的小块内存的自由链表

	bool _isUse = false; // 是否在被使用
};

// 带头双向循环链表
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	Span *Begain()
	{
		return _head->_next;
	}
	Span *End()
	{
		return _head;
	}
	void Insert(Span *pos, Span *newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span *prev = pos->_prev;

		prev->_next = newSpan;
		newSpan->_prev = prev;

		newSpan->_next = pos;
		pos->_prev = newSpan;
	}
	void PushFront(Span *span)
	{
		Insert(Begain(), span);
	}
	bool Empty()
	{
		return _head == _head->_next;
	}
	Span *PopFront()
	{
		Span *front = _head->_next;
		Erase(front);
		return front;
	}
	void Erase(Span *pos)
	{
		assert(pos);
		assert(pos != _head); // 不能删除哨兵位的头结点

		Span *prev = pos->_prev;
		Span *next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}

private:
	Span *_head;

public:
	std::mutex _mutex; // 桶锁
};
